Читать онлайн книгу "КНИГА-ТРЕНАЖЕР: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс"

Книга-тренажер: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме». Авторский курс
Евгений Леонидович Сидоркин


Пособие содержит разбор многих типов задач и рекомендации по решению, а также краткие теоретические справки. Книга предназначена помочь школьникам и начинающим учителям эффективно подготовиться к единому государственному экзамену по информатике на базовом уровне. Книга рассчитана на новый формат сдачи экзамена по ЕГЭ по информатике в компьютерной форме. Разборы решения многих заданий представлены в двух вариантах: на языке Python и аналитическим методом без компьютера.





Книга-тренажер: «Базовая подготовка к ЕГЭ по информатике в компьютерной форме»

Авторский курс



Евгений Леонидович Сидоркин



Учитель информатики Егор Валерьевич Наумов



© Евгений Леонидович Сидоркин, 2023



ISBN 978-5-0055-1904-7

Создано в интеллектуальной издательской системе Ridero




Введение


В данной книге приведена в минимальном количестве теоретическая часть и рассмотрены основные подходы к решению задач компьютерного ЕГЭ по информатике. Наилучшим психологическим подходом на экзамене считается такой: вы решаете все задания, которые легко вам даются, а более сложные пропускаете. После чего, воодушевленные своими успехами в решении задач, приступаете к решению задач, более сложных на ваш взгляд. Далее, если осталось время, то начинаете проверку заданий, которые решили. И напоследок при наличии времени начинаете прорешивать все задания вторым способом и сверяетесь с тем, что у вас получилось при решении первым способом. Если выявились расхождения в ответах, то ищите ошибку. Такая тактика позволит вам набрать максимальное число баллов на экзамене. В книге рассмотрено решение задачи на языке Python, т.к. на нем код получается более коротким в сравнении с другими языками, что поможет сэкономить время на экзамене и набрать более высокий балл. В качестве рекомендации максимального усвоения материала рекомендую читать книгу последовательно по разделам и в конце каждого пробовать самостоятельно решать задания на компьютере, аналитически и сверяться с ответом. После понимания материала, связанного с программированием, пробовать самостоятельно написать код, стараясь не подглядывать, и также решать аналитическим способом, в тех заданиях, где это возможно.

Каждый вариант экзаменационной работы включает в себя 27 заданий, различающихся уровнем сложности и необходимым для их выполнения программным обеспечением.

В работу входят 9 заданий, для выполнения которых, помимо тестирующей системы, необходимо специализированное программное обеспечение (ПО), а именно редакторы электронных таблиц и текстов, среды программирования.

Ответы на все задания представляют собой одно или несколько чисел, или последовательности символов (букв или цифр).

В 2021 г. ЕГЭ по информатике и ИКТ проводится в компьютерной форме, что позволило включить в КИМ задания на практическое программирование (составление и отладка программы в выбранной участником среде программирования), работу с электронными таблицами и информационный поиск. Таких заданий в работе 9, т.е. треть от общего количества заданий.

Максимальный первичный балл за работу – 30.

Общее время выполнения работы – 235 мин.

Экзаменационная работа ЕГЭ охватывает основные темы курса информатики и ИКТ: «Информация и ее кодирование», «Моделирование и компьютерный эксперимент», «Системы счисления», «Логика и алгоритмы», «Элементы теории алгоритмов», «Языки программирования», «Обработка числовой информации», «Технологии поиска и хранения информации».

В книге задания разбиты по темам на основании кодификатора и спецификации контрольных измерительных материалов для проведения в 2021 г. единого государственного экзамена по информатике и ИКТ, подготовленных Федеральным государственным бюджетным научным учреждением «Федеральный институт педагогических измерений». В книге рассмотрены все основные типы задач, которые встречались в тренировочных, репетиционных и диагностических работах, ЕГЭ по информатике основной и досрочной волны 2018—2021 годах.

Прилагаю памятку, которую желательно прочитать перед экзаменом: https://yadi.sk/i/wcTFdrdtA71c8g (https://yadi.sk/i/wcTFdrdtA71c8g).




Глава 1. Моделирование и компьютерный эксперимент





Задача №1. Анализ информационных моделей


Граф – это способ графического представления информации. Объекты в нем – это вершины (узлы), а связи между объектами – ребра (дуги). То есть граф – это набор вершин и связывающих их ребер. Путь в графе – это конечная последовательность вершин, каждая из которых (кроме последней) соединена со следующим ребром. Граф может содержать циклы (первая вершина пути может совпадать с последней). Обычно в задачах используют взвешенный граф, т.е. граф, в котором с каждым ребром связано число (вес). Например, расстояние, стоимость и т. д. Граф обычно задается таблицей, в которой на пересечении строки и столбца с наименованиями вершин записано числовое значение (вес) ребра, соединяющего эти вершины.

Задачи на графы лучше всего решать аналитически, например, в программе «Ножницы», которая стандартно будет у вас открываться на экзамене. Вы можете скопировать картинку, нажать пуск/ найти/ввести слово «ножницы» и в открывшейся программе попытаться рисовать, решая данные задачи тем методом, что будет предложено ниже. Рассмотрим их.



Пример 1.1

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населенных пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта В в пункт Е. В ответе запишите целое число – так, как оно указано в таблице.








Решение:

Из вершины B выходит 5 ребер, значит, в таблице соответствующий пункт должен иметь дороги в 5 других (строка должна содержать 5 заполненных клеток). Такой пункт в таблице один: П6. На графе из вершины Е выходит 4 ребра, значит, в таблице соответствующий пункт должен иметь дороги в 4 других (строка должна содержать 4 заполненные клетки). Такой пункт в таблице один: П4. Таким образом, нам нужно найти расстояние между П6 и П4. На пересечении П6 и П4 находится цифра 20.

Ответ: 20.



Пример 1.2

На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах. Известно, что длина дороги ВД меньше дороги ВЕ. Определите длину дороги ГЖ.

Решение: Для начала расставим количество путей, которые выходят из каждой вершины.








Минимальное число путей из вершин – это 2.








Им соответствует вершина А и Ж. Мы видим в таблице, что в П5 есть два пути. Поэтому предположим, что П5=А, тогда П4=Ж. Т. к. П5 пересекается в значении 10 с П6 и П6=3, то П6=Б. Аналогично получаем, что П7=Д. Далее П7 пересекается с П3, то П3=В. Т. к. П6 пересекается с П2, то П2=В, остается, что П3=Е. Осталась одна вершина – это П1=Г. Условие, что ВЕ> ВД, 23> 16. Это условие истинно, значит, наше предположение изначальное, что П5=А, а П4=Ж, а не наоборот – истинное. А если бы было ложное, тогда что? Тогда бы пришлось рисовать заново, предполагая, что П5=Ж, а П4=А. Смотрим по таблице пересечение П1 и П4 – это число 2.

Ответ: 2.



Пример 1.3

На рисунке слева схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе.

Определите номера пунктов, соответствующих пунктам З и Ж на графе. В качестве ответа запишите два числа в порядке возрастания без разделителей – найденные номера.








Решение:








Пункт К соединяется с вершинами Г (4 вершины) и В (4 вершины). П8 соединяется как раз с двумя вершинами П1 и П2, каждая из которых имеет по 4 дороги, значит, П8=К. Т. к. П8 соединяется с П1 и П2 имеет четыре вершины, то можно предположить, что П1=В, а П2=Г. П1 соединяется с П5, и т. к. П5 имеет 2 вершины, то П5=З. Ранее выяснили, что П2=Г и П2 пересекается с П3, которая имеет 2 вершины, значит, П3=Ж.

Ответ: 35.



Задачи для самостоятельного решения

Задача 1.4

На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта А в пункт В, если передвигаться можно только по указанным дорогам. В ответе запишите целое число – длину пути в километрах.








Задача 1.5

На рисунке схема дорог изображена в виде графа, в таблице звёздочками обозначено наличие дороги между населёнными пунктами.








Так как таблицу и схему рисовали независимо друг от друга, нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Выпишите последовательно без пробелов и знаков препинания, указанные на графе буквенные обозначения пунктов от П1 до П8: сначала букву, соответствующую П1, затем букву, соответствующую П2, и т. д.




Глава 2. Алгебра логики и базы данных





Задание №2. Алгебра логики


Алгебра логики или булева алгебра – так их называют. Как вы думаете, для чего вообще нужна алгебра логики, кроме как мучить детей? Представьте, что по проводу течет ток. Если ток есть в проводе, то обозначим это действие за 1, т.е. истина. Если же тока нет, то ноль, т.е. ложь. Сборка различных схем на компьютере осуществляется как раз схемами, которые представлены на рис.1.

Рисунок №1








Причем можно усложнить схемы, сделать их большими и громоздкими. В компьютере, понятное дело, используются большие логические схемы взаимодействий. Учить это не хочется, но важно понять, как это работает. Для этого и придумали алгебру логики. Какая бы сложная схема ни получилась, ее всегда можно упростить до двух проводов, далее буду говорить до 2 переменных, на языке алгебры логики. Высказывание – повествовательное предложение, о котором можно сказать, истинно оно или ложно. В алгебре простым высказываниям ставятся в соответствии логические переменные (А, В, С и т.д.). Пример высказываний:

Рисунок №2








Логическая переменная – это простое высказывание.

Логические переменные обозначаются прописными и строчными латинскими буквами (a-z, A-Z) и могут принимать всего два значения – 1, если высказывание истинно, или 0, если высказывание ложно.

Логическая формула (логическое выражение) – формула, содержащая лишь логические переменные и знаки логических операций. Результатом вычисления логической формулы является ИСТИНА (1) или ЛОЖЬ (0).

Логическое умножение – конъюнкция. Принятые обозначения: /\, •, и, and. Этой операции соответствует знак умножения. Например, переменные А=0, B=0, то F=A*B=0*1=0. То же самое можно представить в виде примера А=«Немцы победили русских в Великой Отечественной войне»=0, ложь, т.к. русские выиграли, B=«Лимон кислый на вкус»=1, истина, т.к. это соответствует действительности. Тогда A*B=0*1=0, т.к. я настаиваю, чтобы и А, и B выполнялось (через действие умножение), поэтому значением выражения будет ложь. Остальные значения таблицы истинности вы можете посмотреть на Рисунке №3. Логическая формула истинна только в одном случае и ложна в трех других.



Рисунок №3








Логическое сложение (дизъюнкция). Объединение двух (или нескольких) высказываний в одно с помощью союза ИЛИ. Обозначение: \/, +, или, or.



Рисунок №4








На рисунке №4 функция истинна в трех случаях и ложна только в одном, когда ложь. Дизъюнкции соответствует знак сложения.

Отрицание (инверсия), от лат. InVersion – переворачиваю – Рисунок №5:

Соответствует частице НЕ, словосочетаниям НЕВЕРНО, ЧТО или НЕ. Обозначение: не А, ¬А, not. В данной функции значения функции меняются наоборот. Если А=0, то F= Не А=1.

Рисунок №5








Логическая функция импликация. Обозначается cтрелкой ->. В языке программирования соответствует операции меньше либо равно <=. Как из лжи А=0 получить ложь B=0? Рассмотрим на примере A=2> 3 – ложь, то прибавим к обоим частям неравенства +2 и получим тоже ложь B = 4> 5. Если из лжи А=0 и B=0 можно получить ложь, значит, истина A -> B=1. A= -5> 3 – ложь, то обе части неравенства возведу в квадрат и получим уже истину B= 25> 9, тогда при A=0 и B=0 получаю, что А -> B=1. Из истины А=1 я не могу получить B=0, поэтому A -> B=0. Если вы поняли смысл, как мы получили логические высказывания, то вам не потребуется зубрить таблицы истинности.

Рисунок №6








Вы еще не устали от логики)?

Последняя функция эквиваленция. Обозначается как на рисунке №6.

Рисунок №6








Функция истинна A <-> B=1 только в двух случаях: либо когда обе логических переменных А и B истинны, или когда А и B – ложны.

В каком же приоритете выполняются данные операции, спросите Вы? Да все очень просто: сначала отрицание, затем конъюнкция (умножение), потом дизъюнкция (сложение), далее импликация и эквиваленция.

Рисунок №7








В ЕГЭ представлено две задачи на знания алгебры логики. Это задачи №2 и №15. Рассмотрим основные типы этих задач ниже.



Пример 2.1

Логическая функция F задается выражением (x ? y) ? (x ? ¬z) ? (x ? ¬w). Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.








Решение:

Первый способ – это написание программы на языке программирования Python. Код представлен ниже.

print (’x’,’y’,’z’,’w’)
def f (x,y,z,w):
return (not x or y) and (x or not z) and (x == (not w)) # условие из задачи, преобразовали x ? y= not x or y
for x in range (0,2): # изменение переменных от истины до лжи.
for y in range(0, 2):
for w in range(0, 2):
for z in range(0, 2):
if f (x,y,z,w) == 1:  # условие истинности из задачи

print (x,y,z,w)

После запуска программы мы можем заметить строку, содержащую 0 0 0 1. Если сравнить эту строку со строками из таблицы (что в условии), то в данной таблице мы не найдем строку с тремя нулями, поэтому строку 0 0 0 1 можем смело исключить из решения. Рассмотрим оставшиеся три строки, которые необходимо сопоставить с таблицей, что в условии. Второй столбец с тремя единицами соответствует второму столбцу из таблицы, значит, второй столбец – Y. В первую ячейку третьего столбца однозначно можно поставить только ноль, и тогда образуется первая строка 1 1 1 0. Т.к. в последней строчке из рисунка №7 стоит такая же строка 1 1 1 0, что в условиях таблицы, то третий столбец – однозначно W. На рисунке №7 в первой и третьей ячейке третьей строки стоят нули, которые мы можем перенести в таблицу из условия на соответствующие места и однозначно определить, что Z – это первый столбец, а Z – третий.

Рисунок №7
x y z w
0 1 0 1
1 1 0 0
1 1 1 0
Решение:

Второй способ решения этой же задачи состоит в том, что мы составляем таблицу истинности без помощи компьютера. Заполняем первую строку, если w=0, то x=1, а y=1, а z – или ноль, или один. Итого получим почти две одинаковые строчки, за исключением значения z. 1 1 0 0 и 1 1 1 0. Теперь предположим, что W=1, тогда x=0. Т.к. в условии есть столбец с тремя единицами, то необходимо в ручном решении тоже получить такой столбец, поэтому y=1, а z=0. Ответ: ZYWX.

Пример 2.2

Логическая функция F задается выражением (¬z) ? x ? x ? y. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.








Решение:

Расставим скобки, выражение (¬z) ? x ? x ? y является дизъюнкцией двух конъюнкций: ((¬z) ? x) ? (x ? y). В обеих конъюнкциях присутствует x. То есть при x = 0 все выражение равно нулю. Только в третьем столбце напротив нулей стоят значения функции F=0, поэтому третий столбец – это x. Также можно заметить, что выражение ((¬z) ? x) ? (x ? y) =1, если x =1 и выполняется хотя бы одно из условий: y = 1 или z = 0. Из четвертой строки следует, что Перем.1 = z, а Перем.2 = y.

Ответ: zyx.



Пример 2.3

Дан фрагмент таблицы истинности для выражения F. Укажите максимально возможное число различных строк полной таблицы истинности этого выражения, в которых значения x4 не совпадает с F.








Решение:

Таблица истинности выражения с семью переменными (x1…x7) содержит 2


=128 строк. В приведенном фрагменте таблицы x4 не совпадает с F в 4-х строках, а совпадает только в последней нижней строке. Во всех остальных может не совпадать. Тогда максимально возможное количество строк, где значения x4 и F не совпадают, будет 128—1=127.

Ответ: 127.



Задачи для самостоятельного решения

Задача 2.4

Логическая функция F задаётся выражением: (x ? ¬ y) ? (y ? z) ? w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w. В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы. Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.








Задача 2.5

Для функции F известен фрагмент таблицы истинности, представленный ниже. Определите, какое максимальное количество единиц может быть в столбце F полной таблицы истинности, если известно, что при значении x4 = 1 значение функции равно 1.









Задача №3. Файловая система. Базы данных


Возможно, помните из школьного курса информатики, что файл представляет собой имя файла и расширение. Например, mama.doc. Где расширение? Слева от точки – это имя файла, а справа – расширение. Примеры некоторых типов файлов:

Текстовые файлы – расширения. txt,.doc;

Исполняемые файлы – расширения. exe,.com;

Звуковые файлы – расширения. mp3,.waf.

Звездочка «*» – заменяет любое количество (в том числе и нулевое) любых символов.

«?» – заменяет один и только один обязательно стоящий в указанном месте символ. Например, по маске «*.*» будут отобраны вообще все файлы с любыми именами и расширениями, по маске «*.txt» – файлы с расширением. txt, по маске «aл?.doc» – файлы, с расширением. doc, имена которых начинаются на «aл» и имеют обязательный непустой третий символ.

Для хранения и обработки большого объема информации организовывают Базы Данных. Под Базой Данных понимают организованную в соответствии с некоторыми правилами структурированную совокупность логически связанных данных. Эти данные предназначены для удобного совместного хранения и анализа.

Реляционная База Данных состоит из связанных между собой таблиц.

Если установлена сортировка по имени или типу, сравнение идет по кодам символов из кодировочной таблицы. При этом если задана сортировка, к примеру, по имени, то при наличии одинаковых имен сортировка будет применена к расширению файла. Цифра всегда «меньше» буквы.



Пример 3.1

Для групповых операций с файлами используются маски имен файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы: символ»?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. Определите, какое из указанных имен файлов удовлетворяет маске:?fi*r.?xt

1) dir. txt 2) ofir. txt 3) ofir. xt 4) firr. txt

Решение:

Рассмотрим все варианты ответов: 1) не подходит, т.к. в имени отсутствует буква f; 2) полностью удовлетворяет условию маски; 3) не подходит, т.к. на месте»?» после точки отсутствует лишний символ перед буквой x; 4) не подходит, т.к. перед буквой f нет никакого символа, а он должен быть по условию задачи.

Ответ: 2.



Пример 3.2

Каталог содержит файлы с именами

а) p5.pas г) pq. u

б) p4.ppt д) pq.pas

в) p12.pas е) p12.ppt

Определите, в каком порядке будут показаны файлы, если выбрана сортировка по типу (по возрастанию).

1) вадгеб 2) гавдбе

3) вадгбе 4) гвадеб

Решение:

Отсортируем файлы по типу (по возрастанию), а это значит, что сначала отсортируем по расширению, а потом по имени файла. Все расширения начинаются на одну букву p, тогда смотрим расширения. На первом месте будет стоять файл, в расширении которого вообще нет второй буквы – пустой символ всегда меньше непустого: pq. u (г).

Далее идут файлы с расширением. pas (а и д), но поскольку таких файлов несколько, то анализируем имена файлов. Известно, что цифра «меньше» буквы в кодировочной таблице.

p12.pas (в) – т.к. 1 <5

p5.pas (а) – т.к. 5 
pq.pas (д) —

Дальше идут файлы с расширением. ppt, т.к. в расширении ppt вторая буква p больше второй буквы а в расширении pas.

p12.ppt (е) – т.к. 1 <4

p4.ppt (б)

Ответ: 4. pq. u, p12.pas, p5.pas, pq.pas, p12.ppt, p4.ppt



Пример 3.3

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID женщины, ставшей матерью в наиболее молодом возрасте. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.








Решение:

Нарисуем 3 дерева ниже, где матерями будут выступать женщины со следующими ID: 44, 34, 64. По рисунку ниже мы видим, что мать с ID= 44 родила в 26 и 36 лет, мать с ID=34 родила в 26 и 29 лет, а мать с ID=64 родила в 22 и 28 лет. Из чего можем сделать вывод, что 22 года – это самый младший возраст женщины, которая родила ребенка. Поэтому это мать с ID=64.

Ответ: 64.








Задачи для самостоятельного решения

Задача 3.4

Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных, у скольких детей на момент их рождения отцам было больше 25 полных лет. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.








Задача 3.5

Для групповых операций с файлами используются маски имен файлов. Маска представляет собой последовательность букв, цифр и прочих допустимых в именах файлов символов, в которых также могут встречаться следующие символы: символ»?» (вопросительный знак) означает ровно один произвольный символ. Символ «*» (звездочка) означает любую последовательность символов произвольной длины, в том числе «*» может задавать и пустую последовательность. Определите, какое из указанных имен файлов не удовлетворяет маске: bys??.*

1) byste. m 2) bys23.exe 3) bystem. dll 4) byszx.problem




Глава 3. Кодирование и линейные алгоритмы





Задача №4. Кодирование и декодирование информации


Кодирование информации – процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки. Декодирование (операция, обратная кодированию) – перевод кодов в набор символов первичного алфавита. Кодирование может быть равномерное и неравномерное. При равномерном кодировании каждый символ исходного алфавита заменяется кодом одинаковой длины. На примере внизу мы видим, что все буквы имеют одинаковую длину – 2 бита, например, А=00, поэтому код равномерный.








При неравномерном кодировании разные символы исходного алфавита могут заменяться кодами разной длины.








Сообщение однозначно декодируемо с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова. Сообщение однозначно декодируемо с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова.



Пример 4.1

Для передачи сообщений, содержащих только буквы К, Л, М, Н, О, П, Р, решили использовать неравномерный двоичный код, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова, использованные для некоторых букв: К – 11, Л – 000, П – 0010, Р – 1011. Какое кодовое слово надо назначить для буквы М, чтобы код удовлетворял указанному условию и при этом длина слова МОЛОКО после кодирования была наименьшей? Если таких кодов несколько, укажите код с наименьшим числовым значением.

Решение:








Изобразим буквы К, Л, П, Р на дереве (рекомендую на экзамене прямо так и рисовать мышкой, как у меня выше нарисовано). По условию задачи необходимо, чтобы слово не являлось началом другого кодового слово, т.к. необходимо, чтобы выполнялось прямое условие Фано. Необходимо поставить в дерево две буквы: О и М, чтобы условие Фано выполнялось. Как это сделать? Т.к. буква О в слове «молоко» встречается 3 раза, то мы поставим эту букву на меньшую глубину дерева (01), чтобы получить наименьший код. Букву М, которая встречается всего 1 раз, поставим на большую глубину дерева (100). Итого имеем следующие длины: М=100=3, О=01=2*3 (т.к. 3 раза встречается, поэтому умножаем на 3) =6, Л=000=3, К=11=2. Длина кода равна=3+6+3+2=14.

Ответ: 14.



Рассмотрим задачу на обратное условие Фано.



Пример 4.2

По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв А, Б используются такие кодовые слова: А: 00011, Б: 1001, В: 01100. Укажите кратчайшее кодовое слово для буквы Г, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наибольшим числовым значением.

Решение:

Для выполнения прямого условия Фано букву Г мы можем поставить на свободную ветку дерева, то Г=11 (кратчайший путь), т.к. этот путь не будет являться ничьим началом кодового слова. При обратном условии Фано букву Г=10 можем поставить (кратчайший путь), т.к. 10 не является окончанием ни одного из приведенных кодовых слов в условии. Г=00 взять не можем, т.к. 00 является окончанием В, и тогда не выполняется обратное условие Фано. Из двух чисел 11 и 10 наибольшее – 11.

Ответ: 11.



Пример 4.3

Для передачи данных по каналу связи используется 5битовый код. Сообщение содержит только буквы А, Б и В, которые кодируются следующими кодовыми словами: А – 11010, Б – 10111, В – 01101. При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку». ) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка (она обозначается «х»). Получено сообщение 11000 11101 10001 11111. Декодируйте это сообщение – выберите правильный вариант.

1) АххБ 3) хххх

2) АВхБ 4) АВББ

Решение:

Декодируем каждое слово сообщения. Первое слово: 11000 отличается от буквы А только одной позицией, поэтому на первом месте будет А. Второе слово: 11101 отличается от буквы В только одной позицией, поэтому на второй позиции будет В. Третье слово: 10001 отличается от любой буквы более чем одной позицией, поэтому третья позиция – x. Четвёртое слово: 11111 отличается от буквы Б только одной позицией, поэтому четвертая позиция – Б. Таким образом, ответ: АВхБ.

Ответ: 2.



Задачи для самостоятельного решения

Задача 4.4

По каналу связи передаются сообщения, содержащие только четыре буквы: М, А, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: М – 101, Р – 100, Т – 01. Укажите кодовое слово минимальной длины, которое можно использовать для буквы А. Если таких кодовых слов несколько, приведите кодовое слово с минимальным числовым значением.

Примечание. Условие Фано означает, что соблюдается одно из двух условий: либо никакое кодовое слово не является началом другого кодового слова, либо никакое кодовое слово не является окончанием другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.



Задача 4.5

По каналу связи передаются сообщения, содержащие только шесть букв: Я, Н, В, А, Р, Ь. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Н – 00, В – 01, Р – 10, Ь – 111. Укажите минимально возможную длину закодированной последовательности для слова ВАРВАР.




Задача №5. Анализ, исполнение и построение линейного алгоритма для исполнителя


Алгоритм – это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.

Алгоритм можно задать одним из следующих способов:

• словесное описание последовательности действий на

естественном языке;

• графическое изображение в виде блок-схемы;

• запись при помощи псевдокода (алгоритмического

языка);

• запись на языке программирования.

В этом типе задач рассматривается в основном словесное описание алгоритмов на естественном языке, а потому никаких специальных знаний для решения задачи не требуется. В данных типах задач используются разные исполнители – от чертежника, черепашки до автомата. Рассмотрим основные типы задач, которые здесь могут быть использованы.



Пример 5.1

Алгоритм получает на вход натуральное число N и строит по нему новое число R следующим образом:

1. Строится двоичная запись числа N.

2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.

3. Предыдущий пункт повторяется для записи с добавленной цифрой.

4. Результат переводится в десятичную систему.

Пример. Дано число N = 13. Алгоритм работает следующим образом:

1. Двоичная запись числа N: 1101.

2. Сумма цифр двоичной записи 3, остаток от деления на 2 равен 1, новая запись 11011.

3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.

4. Результат работы алгоритма R = 54.

При каком наименьшем числе N в результате работы алгоритма получится R> 170? В ответе запишите это число в десятичной системе счисления.

Решение: Рассмотрим первое попавшееся число, которое больше 170. 171=10101011. У этого числа отделим последние два разряда 171= 101010 | 11 не походит, т.к., выполняя второе правило, алгоритм сложит все единицы, которые стоят слева от вертикальной линии 1+1+1=3, а затем 3 разделим на 2 без остатка и получим 1 и запишем эту единица справа от числа 101010 1. Затем снова применим второе правило к получившемуся числу 101010 | 1. И получим уже новое число 101010 | 10. Получившееся число 10101010=170 по условию задачи должно быть равно 171. Понятно, что 171 не равно 170, поэтому число 171 не подходит. Берем число 172=10101100. Проверяем его на второе правило 2 раза и видим, что число 172 подходит. Осталось только число 10101100 без двух правых нулей перевести в десятичную систему счисления. Получаем 101011=43.

Ответ: 43.



Решение задачи cпособом программирования на языке Python:

for n in range (42,64):
r = list ( bin (n)[2:]) # преобразуем число сначала в двоичную систему счисления и потом переводим его список строк
for i in range(len(r)):
r[i] = int(r[i]) # преобразуем каждую строку (двоичная цифра) в целый тип данных

r += [sum(r)%2] # добавляем остаток от деления справа от числа
r += [sum(r) % 2] # добавляем остаток от деления справа от числа
for i in range(len(r)):
r[i] = str(r[i]) # обратный перевод в список строк
if int(''. join(r), 2) >170:# переводим в целочисленный тип и проверяем на условие задачи
print (n)
break

Ответ: 43.



Пример 5.2

На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются разряды по следующему правилу:

если два последних разряда одинаковые, дописывается 0, иначе дописывается 1.

3) К полученной записи дописывается еще один бит по правилу в пункте 2.

Полученная таким образом запись является двоичной записью искомого числа R.

Укажите минимальное число N, при вводе которого получится значение R больше, чем 61.

В ответе полученное число запишите в десятичной системе.



Решение:

Узнаем, какое число N может быть, чтобы в результате получилось 61.

61 = 111101 




Убираем два младших разряда и исполняем алгоритм.

15=1111 


 -> (если два последних разряда одинаковые, то применяем первое правило) -> 11110


 -> (два последних разряда разные) -> 111101 


= 61.

Следовательно, из числа N = 15 


 получается R = 61


Значит, для того чтобы получить число большее 61, необходимо взять следующее N = 16.

Второй способ решения этой задачи заключается в том, что, как и в первой задаче, мы перебираем по порядку все числа большие 61. Числа 62, 63 под условие алгоритма не подходят, т.к. два последних разряда не соответствуют двум алгоритмам из условия, т.е., например, 62= 111110


, где, откидывая 2 последних разряда, получаем число 11111


и из данного мы не можем получить число 111110


, применив 2 алгоритма из условия. 64=1000000


 под условие алгоритма походит, отбрасываем два правых разряда по условию задачи и получаем 10000


=16.

Ответ: 16.



Пример 5.3

Автомат получает на вход четырехзначное число. По этому числу строится новое число по следующим правилам.

1. Умножаются первая и вторая, а также третья и четвертая цифры исходного числа.

2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходное число: 5431. Произведения: 5 * 4 = 20; 3 * 1 = 3. Результат: 320. Укажите максимальное число, в результате обработки которого автомат выдаст число 1216.

Решение:

Рассмотрим число 1216. Так как это два произведения двух одноразрядных чисел, имеем два числа 12 и 16.

12 = 2*6 = 3*4

16 = 2*8

Максимально возможная цифра в найденных произведениях – 8. Т.к. необходимо получить максимальное число по условию задачи, значит, максимальное искомое число начинается на 82. Для получения 12 используется максимальное число – 6. Следовательно, оставшиеся два разряда 62.

Ответ: 8262.



Пример 5.4

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, —3) переместит Чертёжника в точку (6, —1).

Цикл

ПОВТОРИ число РАЗ

последовательность команд

КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным).

Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и смещения в первой из повторяемых команд неизвестны):

НАЧАЛО
сместиться на (—1, 4)
ПОВТОРИ… РАЗ
сместиться на (…, …)
сместиться на (—1, —2)
КОНЕЦ ПОВТОРИ
сместиться на (—23, —12)

КОНЕЦ

После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ… РАЗ»?

Решение:

Будем считать, что Чертёжник находится в начале координат. После выполнения команды сместиться на (—1, 4) Чертёжник окажется в точке с координатами (—1, 4). После выполнения цикла Чертёжник переместится, по оси икс Чертёжник сместится на -1+n (-1+x) -23 и по игреку на 4+n (-2+y) -12, где n, x, y – неизвестные. В результате последнего перемещения Чертёжник должен переместиться в начало координат, то есть:

– 1+n (-1+x) -23=0 и 4+n (-2+y) -12=0

В первом и втором уравнении перенесем цифры в правую часть и получим 1+23=24 и 12—8=8. Остается только найти наибольший общий делитель чисел 24 и 8. Это число 8.

Ответ: 8.



Пример 5.4

Исполнитель Робот существует в лабиринте – поле, представленном в виде квадрата 6х6. Робот имеет две команды: влево и вниз, вверх, вниз, которые перемещают его на клетку влево или вниз соответственно. При попытке выхода за границы лабиринта или столкновения со стеной Робот разрушается.

Цикл

ПОКА условие

последовательность команд

КОНЕЦ ПОКА

выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2

КОНЕЦ ЕСЛИ

выполняется команда1 (если условие истинно) или команда2 (если условие ложно).

Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и закончит работу в клетке начала движения?



НАЧАЛО

ПОКА <снизу свободно>

вниз

КОНЕЦ ПОКА

ПОКА <слева свободно>

влево

КОНЕЦ ПОКА

ПОКА <сверху свободно>

вверх

КОНЕЦ ПОКА

ПОКА <справа свободно>

вправо

КОНЕЦ ПОКА

КОНЕЦ


Решение:

1) Заметим, что в общем случае Робот идет сначала до стены вниз, затем влево, потом вверх и заканчивает маршрут движением вверх, до стены.

Один из главных приёмов в решении этой задачи – проверять клетки группами, а не по одной.

Проверим почти все клетки Робота на предмет того, подходит ли алгоритм:








– A6 – маршрут вниз-вверх – подходит;

– F6 – маршрут влево-вправо – подходит;

– D5 – маршрут вниз-влево, вверх, вправо – подходит;

– E5 – маршрут вниз-влево, вверх, вправо (остановка в D5) – не подходит;

– B4 – маршрут вниз-вверх-вправо (остановка в D4) – не подходит;

– C4 – не двигается, стоит на одном месте – подходит;

– C2 – не двигается, стоит на одном месте – подходит;

– F5 – маршрут вниз-вверх – подходит;

– F4 – вниз-вверх (остановка F5) – не подходит;

– F3 – вниз-вверх (остановка F5) – не подходит;

– F2 – вниз-вверх (остановка F5) – не подходит;

– F1 – вверх (остановка F5) – не подходит;

– A2 – вверх (остановка в А6) – не подходит;

– A1 – не двигается – подходит;

– E1 – влево-вверх-вправо (остановка в D4) – не подходит.

Задача, конечно, нудная, т.к. проверять нужно все клетки, в которых вы сомневаетесь. Понятно, что клетки пустые, где нет стенок, в них Робот начать и остановиться не сможет, поэтому эти клетки можно не проверять. Иногда такие задачи дают на экзамене, и лучше вычеркивать клетки в приложении «Ножницы». Здесь нужна высокая степень концентрации.

Ответ: 7.



Задачи для самостоятельного решения

Задача 5.5

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописывается сначала ноль, а затем единица. В противном случае, если N нечётное, справа дописывается сначала единица, а затем ноль.

Например, двоичная запись 100 числа 4 будет преобразована в 10001


, а двоичная запись 111 числа 7 будет преобразована в 11110


.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа R – результата работы данного алгоритма.

Укажите минимальное число R, которое больше 102 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.



Задача 5.6

Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Например, если Чертёжник находится в точке с координатами (4, 2), то команда сместиться на (2, —3) переместит Чертёжника в точку (6, —1).

Цикл

ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ

означает, что последовательность команд будет выполнена указанное число раз (число должно быть натуральным). Чертёжнику был дан для исполнения следующий алгоритм (количество повторений и смещения в первой из повторяемых команд неизвестны):

НАЧАЛО
сместиться на (4, 6)
ПОВТОРИ… РАЗ
сместиться на (…, …)
сместиться на (-1, -2)
КОНЕЦ ПОВТОРИ
сместиться на (20, 30)
КОНЕЦ

После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «ПОВТОРИ… РАЗ»?



Задача 5.7

Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, включает в себя 4 команды-приказа и 4 команды проверки условия.

Команды-приказы: вверх, вниз, влево, вправо

При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ?, вниз ?, влево ?, вправо ?.

Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится, и программа прервётся.

Другие 4 команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:





Конец ознакомительного фрагмента. Получить полную версию книги.


Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, купив полную легальную версию (https://www.litres.ru/evgeniy-leonidovich/kniga-trenazher-bazovaya-podgotovka-k-ege-po-informat/) на ЛитРес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.



Если текст книги отсутствует, перейдите по ссылке

Возможные причины отсутствия книги:
1. Книга снята с продаж по просьбе правообладателя
2. Книга ещё не поступила в продажу и пока недоступна для чтения